//1.笨方法
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<unsigned int> dp(1e4+10,INT_MAX); // INT_MAX+1会溢出int
        
        sort(coins.begin(), coins.end());
        if(amount==0)
            return 0;
        dp[0]=0;
        for(int i = 1; i <= amount; ++i) {
            for(int j = 0; (j < coins.size()) && (i - coins[j] >= 0); ++j) {   // (j < coins.size()) && (i - coins[j] >= 0) 越界判断在前面，索引必须>=0
                dp[i] = min(dp[i], dp[i-coins[j]] + 1);
            }
        }
        if(dp[amount] == INT_MAX) //如果没有被修改初始值，就证明没有方案
            return -1;
        return dp[amount];
        
    }
};
//2.笨方法完善--不要排序增加复杂度----开辟空间不要1e4+10

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<unsigned int> dp(amount+1,INT_MAX);
        // INT_MAX+1会溢出int
        
        if(amount==0)
            return 0;

        dp[0]=0;
        for(int i = 1; i <= amount; ++i) {
            for(int j = 0; j < coins.size(); ++j) {
                if(coins[j] <= i)
                    dp[i] = min(dp[i], dp[i-coins[j]] + 1);
            }
        }
        if(dp[amount] == INT_MAX)
            return -1;
        return dp[amount];
        
    }
};



